The present invention relates to a method and apparatus for realistically animating the motion and interaction of objects in a display system. More particularly, the present invention relates to a circuit or subsystem having a parallel computational architecture and a method for using same within a system. The parallel hardware architecture allows real-time resolution of complex physics-based data problems, such as Linear Complementarity Problems (LCPs). Such problems arise, for example, during operation of a rigid body dynamics engine within a system having a visual display. The present invention finds application within systems such as a conventional Personal Computers (PCs) and game consoles, as well as recently proposed systems incorporating a hardware-based, physics processing unit.
Physics-based “animations” and “simulations” (hereafter these terms are used interchangeably regardless of application, specific method of display, or means of communicating related physics-based data) have been extensively investigated during the past three decades. Such animations are useful in a range of applications including virtual reality, electronic/computer games, scientific simulations, and robotic motion planning. Game developers, for example, increasingly use real-time, physics-based animations to enhance the realism of game object interactivity. Integral to the development of real-time, physics-based animations is the dynamic simulation of rigid body movements and interactions.
The term “rigid body” is used to describe animated objects that do not deform. They are said to be stiff even when colliding with other objects or with the environment defined by the animation. A rigid body simulation involves a complex sequence of computational steps causing animated bodies and related forces to interact in a realistic manner according to a set of defined physical rules, or so-called “constraints.” One goal of a rigid body simulator is to minimize or prevent the penetration of objects. If a simulator were to allow large penetrations of objects, then the illusion of object rigidity would be lost.
The practical development of physics-based animations, including rigid body simulations, has proved quite difficult. For simple cases, continuous real life problems can be written using continuous mathematics and solved algebraically. This approach is to high school physics students. However, the set of cases which have algebraic solutions is very small and a rigid body simulator must be able to handle any configuration of contacting rigid bodies. For this reason, a discrete problem is chosen that approximates the continuous problem. A discrete problem can be represented with a finite amount of data and can be evaluated numerically (by a computer) at discrete time intervals. Given that frames of animation are only required at discrete time intervals, this is an acceptable limitation.
Selecting a discrete model that approximates a sufficiently large class of continuous problems and is solvable in real time by a computer is difficult. A poor choice of discrete model can result in behavior that diverges unacceptably from the original continuous problem. For example with a bad model, objects might jump around for no reason, penetrate unacceptably, fall through a floor, or fly off into infinity.
At least in the context of computer games, the accuracy of discrete approximations with respect to the continuous problem is not particularly important, within certain limits. This result arises because unlike simulations used in science and engineering, computer game animations need not be predictive. Any plausible discrete model will do. However, although this relaxed requirement makes it easier to meet the real-time constraint, it unfortunately doesn't make the mathematics any easier.
Numerous issues must be addressed when building a system adapted to run real-time, physics-based animations. For example, the geometry of objects plays an important role in determining the physics of motion, as well as the physics of contact between objects. An object may be a single rigid body such as a chair or house, or may consist of a number of connected (e.g., jointed) bodies, such as a human figure. Collision or contact between objects must be accurately determined. Solving the necessary equations of motion to realistically animate objects has proved to be a difficult problem since accuracy (i.e., realism) and computational speed are always at odds.
In addition to preventing object/object or object/environment penetration, a system visually displaying the dynamic movement and interaction of rigid bodies must take into account various physical properties of the objects. Mass is one example of a physical property. Physics-based animations must also faithfully track and account for forces upon the animated objects. Gravity is one example of a force. A rigid body simulator, or “engine,” associated with the display system must also create the illusion that simulated objects have certain surface properties, such as friction.
As one might expect, the modeling and simulation of the complexities arising from varied object geometries, interacting objects and forces, and changing object constraints requires a great deal of sophisticated mathematics. However, the mathematics implicated in the present invention are conventional in their general nature. That is, those of ordinary skill in the art will understand the mathematical bases upon which the present invention is predicated. It is neither appropriate nor required that this present description teach the entire body of implicated mathematics. Nevertheless, some discussion of mathematical model(s) is required in order to establish a common descriptive vocabulary.
The conventional resources typically available in a display system implementing physics-based animations are conceptually illustrated in FIG. 1. Those of ordinary skill in the art will recognize that the hardware/software designations in this example are relatively arbitrary. For example, computational logic may be fully implemented in software, hardwired, or some combination of software and hardware according to a system designer's discretion. However, some logical distinction between hardware and software as exemplified by current best practices is useful in the description that follows.
In FIG. 1, a Central Processing Unit (CPU) 1, such as a Pentium® microprocessor, together with its associated drivers and internal memory, access data from an associated external main memory 2, and/or one or more peripheral devices 3, typically including a display. The terms “internal” and “external” are used to generally differentiate between various memories in relation to the other computational components in a system. Such differentiation is clearly relative, since most internal memory can be turned into external memory and vice verses. Generally speaking, however, an internal memory is typically co-located on the same integrated circuit (IC) chip as related computational component(s), while external memory is typically implemented on a separate chip or chip set.
A main application 4 is resident in main memory 2 and/or peripheral 3 (e.g., a magnetic or optical disk, a solid-state memory device such as a PROM, EPROM, or EEPROM, a cartridge for a game console or similar device). Main program 4 typically uses one or more Application Programming Interfaces (APIs) to access blocks of specialty software associated with various program functions. An API is a well understood programming technique used to establish a lexicon of sorts by which one piece of software may “call” another piece of software. The term “call” as variously used hereafter broadly describes any interaction by which one piece of software causes the retrieval, storage, indexing, update, execution, etc., of another piece of software.
Data instructions, often in a prescribed packet form and referred to hereafter as “commands,” are generally used to initiate calls between one or more software or hardware components. Execution (i.e., “running”) of software, in any of its various forms including micro-code, occurs upon receipt of an appropriate command.
Conventional systems implementing physic-based animations routinely include or incorporate by functional “call” a related piece(s) of specialty software referred to generically hereafter as a “physics engine.” A physics engine may be thought of as an operative collection of resources, including specialized software, implementing physics effects within a main application.
With the recent and growing appetite for realism, physics engines have been added to the program code implementing, for example, PC games. Indeed, a market has emerged directed to the development physics engines or so-called “physics middleware.” Companies like HAVOK, MathEngine, Criterion, and Meqon Research have developed specialty software that may be called by a main application to better incorporate natural looking, physics-based interactions into a main application.
Prior to the use of physics engines in games, objects were animated by hand. These animations were triggered in response to input from the user. For example, if the user pressed a punch key, the game would play a corresponding punch animation. If the user pressed the punch key while standing next to a pile of boxes, then an animation of the pile of boxes falling over might have been played. If the user pressed the punch key while standing next to a game character, an animation of that character falling to the floor might have been played.
Since the animated motion displayed by the game was specified by a set of pre-drawn animations, the punch, the falling boxes, and the falling character would each move in the same manner every time. As well as being quite boring for the user, the animation could not take into account the context of the action. For example, if the user pressed the punch key next to a wall, there would often be nothing to stop the player's arm going through the wall. If the user had previously parked a car behind the pile of boxes, the boxes would typically fall through the car. If the user punched a character next to a cliff, the punched character would typically fall flat and lie in midair over the cliff rather than falling over the cliff ledge.
These problems were overcome conventionally by limiting the user's actions, for example by not giving the user a car to drive, not allowing the user to walk within arm's length of a wall and not allowing fights next to cliffs. These restrictions were often frustrating to the user. Another way around the problem was to simply generate outcome animations for every possible combination of user actions. However, as the number of possible user actions grows, the number of outcome animations outcomes also grows. Thus, as game complexity increases the cost associated with the development of multiple animations becomes prohibitive.
Games designed using only pre-drawn animations start with a completely restricted environment where nothing unscripted can happen. This completely restricted environment is gradually made more interactive as an animator produces more and more animations. In contrast, games designed using physics-based approaches start from the opposite point of view, namely objects initially have complete freedom of motion. The game designer then, for example, designs a solid environment and adds a constraint that objects can still move with complete freedom, except that they must not fall through the solid environment. In a physics-based game, there is no reason why the user can't be given a car, or be allowed to punch a person next to a cliff, so those constraints are never introduced. As the game design progresses, some additional constraints are added, however, as most fun games have some set of defining rules.
Rather than supplying a set of animations for each object, the game designer specifies a set of physical properties for the object such as mass, friction, and in some cases even elasticity. The physics engine then uses the laws of physics to move the objects as if they had these properties, so long as the movement don't violate a specified constraint. A game designer incorporates physics-based effects by deciding what forces and torques to apply to object(s) in response to user input.
Of necessity, physics engines include a rigid body dynamics engine adapted to calculate the movement of rigid bodies within an animation. As will be appreciated by those of ordinary skill in the art, a rigid body dynamics engine will typically form one aspect of a larger physics engine. The exact programming and/or resource boundaries between the rigid body dynamics engine and other effects engines within the physics engine are a matter of design choice, and it is expected that the rigid body dynamics engine will draw upon a library of functions and/or a pool of common resources provided by the physics engine and/or by the main application.
Unfortunately, contemporary physics engines have significant limitations as to the number of objects in an animated scene, and more particularly, the number of active (i.e., moving or interacting) objects. Realistic visual images of physics-based interaction must account for constraints placed upon many or all of the objects. As noted above, a constraint is a restriction on the possible movement or interaction of an object (e.g., a door hinge, a knee joint, a dog on a leash). Increasing complexity of terrain geometry greatly increases the difficulty of simulating object interactions with the terrain. The complexity of collision detection and resolution also increases with the complexity of an object's surface geometry (i.e., its surface detail).
Along with an increasing number of active objects, cutting edge animations and simulations demand an increased number of forces being applied to the objects. These aggregate demands are further aggravated by the increasing number of “time steps” per second being used in animations (i.e., the frequency with which the animated world with all its objects and forces is updated in real time).
However, among the factors challenging the realistic, real-time animation of objects in a physics-based application, the definition and incorporation of constraints upon the animated rigid body objects has proved most difficult. Indeed, it the existence of numerous constraints that makes the underlying mathematical (numerical analysis) problem much more difficult to resolve, as compared with a simple application of Newton's laws of motion. In mathematical terms, it is constraints upon the movement of objects within a physics-base problem that gives rise to many of the difficulties associated with solving the LCPs expressing the physics-based problem.
Many attempts have been made to address the difficulty task of resolving complex bounded value problems, such as LCPs, in an accurate efficient manner. To date, however, these attempts have proved so slow that only relatively small physics-based problems have been successfully animated in real-time. Once the number of the objects, forces, and/or constraints upon objects in a physics-based animation rises above a relatively small value, the mathematics underlying the animation simply can not be resolved in real-time using conventional computational methods and/or conventional hardware platforms. The term “real-time” describes the quality of a visual display having a frame rate sufficiently fast to give a viewer the illusion of continuous, realistic-appearing movement.
As is also well understood by those of ordinary skill in the art, the mathematical resolution of LCPs in a digital computational environment, such as a PC, involve the execution of a numerous floating point operations. While general purpose processors, like the Pentium family of microprocessors, are capable of executing floating point operations, they are not able capable of executing the great number of floating operations typically required for the real-time animation of physics-based interactions.
Simply stated, the well-recognized and growing desire for real-time physics-based animations within next-generation applications remains unmet. This failure is really two-fold. First, conventional computational methods are too inefficient to solve complex LCPs in real-time. Second, conventional hardware platforms do not enable a the speed of data transfer and the number of mathematical operations required to animate complex physics-based interactions in real-time.